home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 3: Developer Tools / Linux Cubed Series 3 - Developer Tools.iso / utils / disk-man / mtools-3.000 / mtools-3 / mtools-3.0 / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-05-03  |  3.7 KB  |  183 lines
  1. /*
  2.  * hash.c - hash table.
  3.  */
  4.  
  5. #include "sysincludes.h"
  6. #include "htable.h"
  7. #include "mtools.h"
  8.  
  9. struct hashtable {
  10.   T_HashFunc f1,f2;
  11.   T_ComparFunc compar;
  12.   int size,fill; 
  13.   int max;
  14.   int needrehash;
  15.   T_HashTableEl *entries;
  16. };
  17.  
  18. static int sizes[]={5, 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421, 12853,
  19.             25717, 51437, 102877, 205759, 411527, 823117, 1646237,
  20.             3292489, 6584983, 13169977, 26339969, 52679969, 105359939,
  21.             210719881, 421439783, 842879579, 1685759167, 0 };
  22. static int deleted=0;
  23. static int unallocated=0;
  24.  
  25. static int alloc_ht(T_HashTable *H, int size)
  26. {
  27.   int i;
  28.  
  29.   for(i=0; sizes[i]; i++)
  30.     if (sizes[i] > size*2 )
  31.       break;
  32.   if (!sizes[i])
  33.     for(i=0; sizes[i]; i++)
  34.       if (sizes[i] > size)
  35.     break;
  36.   if(!sizes[i])
  37.     return -1;
  38.   size = sizes[i];
  39.   H->max = size * 4 / 5 - 2;
  40.   H->size = size;
  41.   H->fill = 0;
  42.   H->needrehash = 0;
  43.   
  44.   H->entries = NewArray(size, T_HashTableEl);
  45.   if (H->entries == NULL)
  46.     return -1; /* out of memory error */
  47.   
  48.   for(i=0; i < size; i++)
  49.     H->entries[i] = &unallocated;
  50.   return 0;
  51. }
  52.  
  53. int make_ht(T_HashFunc f1, T_HashFunc f2, T_ComparFunc c, int size,
  54.         T_HashTable **H)
  55. {
  56.   *H = New(T_HashTable);
  57.   if (*H == NULL){
  58.     return -1; /* out of memory error */
  59.   }
  60.   
  61.   (*H)->f1 = f1;
  62.   (*H)->f2 = f2;
  63.   (*H)->compar = c;
  64.  
  65.   if(alloc_ht(*H,size))
  66.     return -1;
  67.   return 0;
  68. }
  69.  
  70. int free_ht(T_HashTable *H, T_HashFunc entry_free)
  71. {
  72.   int i;
  73.   if(entry_free)
  74.     for(i=0; i< H->size; i++)
  75.       if (H->entries[i] != &unallocated &&
  76.       H->entries[i] != &deleted)
  77.     entry_free(H->entries[i]);
  78.   Free(H->entries);
  79.   Free(H);
  80.   return 0;
  81. }
  82.  
  83. /* add into hash table without checking for repeats */
  84. static int _hash_add(T_HashTable *H,T_HashTableEl *E)
  85. {
  86.   int f2, pos;
  87.  
  88.   pos = H->f1(E) % H->size;
  89.   f2 = -1;
  90.   while(H->entries[pos] != &unallocated &&
  91.     H->entries[pos] != &deleted){
  92.     if (f2 == -1)
  93.       f2 = H->f2(E) % (H->size - 1);
  94.     pos = (pos+f2+1) % H->size;
  95.   }
  96.   H->entries[pos] = E;
  97.   H->fill++;
  98.   return 0;
  99. }
  100.  
  101. static int rehash(T_HashTable *H)
  102. {
  103.   int size,i;
  104.   T_HashTableEl *oldentries;
  105.   /* resize the table */
  106.   
  107.   size = H->size;
  108.   oldentries = H->entries;
  109.   if(alloc_ht(H,H->fill+1))
  110.     return -1;
  111.  
  112.   for(i=0; i < size; i++){
  113.     if(oldentries[i] != &unallocated && oldentries[i] != &deleted)
  114.       _hash_add(H, oldentries[i]);
  115.   }
  116.   Free(oldentries);
  117.   return 0;
  118. }
  119.  
  120. int hash_add(T_HashTable *H, T_HashTableEl *E)
  121. {
  122.   if (H->fill >= H->max || H->needrehash)
  123.     rehash(H);
  124.   if (H->fill == H->size)
  125.     return -1; /*out of memory error */
  126.   return _hash_add(H,E);
  127. }
  128.  
  129.  
  130. /* add into hash table without checking for repeats */
  131. int hash_lookup(T_HashTable *H,T_HashTableEl *E, T_HashTableEl **E2,
  132.         int *hint)
  133. {
  134.   int f2, pos, upos, ttl;
  135.  
  136.   pos = H->f1(E) % H->size;
  137.   ttl = H->size;
  138.   f2 = -1;
  139.   upos = -1;
  140.   while(ttl &&
  141.     H->entries[pos] != &unallocated &&
  142.     (H->entries[pos] == &deleted ||
  143.      H->compar(H->entries[pos], E) != 0)){
  144.     if (f2 == -1)
  145.       f2 = H->f2(E) % (H->size - 1);
  146.     if (upos == -1 && H->entries[pos] == &deleted)
  147.       upos = pos;
  148.     pos = (pos+f2+1) % H->size;
  149.     ttl--;
  150.   }
  151.   if(H->entries[pos] == &unallocated || H->entries[pos] == &deleted)
  152.     return -1;
  153.   if (upos != -1){
  154.     H->entries[upos] = H->entries[pos];
  155.     H->entries[pos] = &deleted;
  156.     pos = upos;
  157.   }
  158.   if(hint)
  159.     *hint = pos;
  160.   *E2= H->entries[pos];
  161.   return 0;
  162. }
  163.  
  164. /* add into hash table without checking for repeats */
  165. int hash_remove(T_HashTable *H,T_HashTableEl *E, int hint)
  166. {
  167.   T_HashTableEl *E2;
  168.  
  169.   if (hint >=0 && hint < H->size &&
  170.       H->entries[hint] != &unallocated && H->entries[hint] != &deleted &&
  171.       H->compar(H->entries[hint], E)){
  172.     H->fill--;
  173.     H->entries[hint] = &deleted;
  174.     return 0;
  175.   }
  176.  
  177.   if(hash_lookup(H, E, &E2, &hint))
  178.     return -1;
  179.   H->fill--;
  180.   H->entries[hint] = &deleted;
  181.   return 0;
  182. }
  183.